/*
 * Copyright 2011-2012 by The Regents of the University of California Licensed
 * under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. you may obtain a copy of the
 * License from
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package edu.ucsd.db.bassarisk.query.expression.visitor;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import edu.ucsd.db.bassarisk.exception.VisitorException;
import edu.ucsd.db.bassarisk.query.expression.Expressions;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanAnd;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanNot;
import edu.ucsd.db.bassarisk.query.expression.Expressions.BooleanOr;
import edu.ucsd.db.bassarisk.query.expression.Expressions.Expression;
import edu.ucsd.db.bassarisk.query.expression.Expressions.NonterminalExpr;

public class BooleanSimplificationTransformation extends
    ExpressionTreeTransformation<Void> {
  /**
   * Find any nested boolean expressions of same type (AND in AND, OR in OR) and
   * flatten them while preserving the order of the inputs (positional
   * predicates depend on this order in early pipeline stages).
   */
  private <T extends NonterminalExpr> Expression
      flattenBoolean(final T expr, final Class<T> tClass) throws VisitorException {
    // Flatten
    Stack<Expression> inputStack = new Stack<Expression>();
    this.pushExpressions(inputStack, expr.getSubExprs());
    List<Expression> newSubExprs = new ArrayList<Expression>();
    while (!inputStack.isEmpty()) {
      Expression input = inputStack.pop();
      if (input.getClass() == tClass) {
        this.pushExpressions(inputStack, ((NonterminalExpr) input).getSubExprs());
      } else {
        newSubExprs.add(input.accept(this, null));
      }
    }
    // Remove the AND/OR expression if it only has one nested input.
    if (newSubExprs.size() > 1) {
      return expr.transform(newSubExprs);
    } else if (newSubExprs.size() == 1) {
      return newSubExprs.get(0);
    } else {
      String msg =
          "Internal Error: Boolean expression with no input should have been "
              + "caught in typechecking.";
      throw new RuntimeException(msg);
    }
  }

  /**
   * Push expression from list onto stack (such that the first expression in the
   * list is at the top of the stack).
   */
  private void pushExpressions(final Stack<Expression> exprStack,
                               final List<Expression> exprList) {
    for (int i = exprList.size() - 1; i >= 0; --i) {
      exprStack.push(exprList.get(i));
    }
  }

  @Override
  public Expression visitBooleanAnd(final BooleanAnd expr, final Void arg)
      throws VisitorException {
    return this.flattenBoolean(expr, BooleanAnd.class);
  }

  @Override
  public Expression visitBooleanNot(final BooleanNot expr, final Void arg)
      throws VisitorException {
    Expression newSubExpr = expr.getSubExpr().accept(this, arg);
    if (newSubExpr instanceof BooleanNot) {
      return ((BooleanNot) newSubExpr).getSubExpr().accept(this, null);
    } else {
      return expr.transform(Expressions.list(newSubExpr));
    }
  }

  @Override
  public Expression visitBooleanOr(final BooleanOr expr, final Void arg)
      throws VisitorException {
    return this.flattenBoolean(expr, BooleanOr.class);
  }
}
